In modern computing systems a variety of storage devices may be employed for storing and for accessing software and/or data. Typically these may include magnetic storage devices such as hard disk drives (HDDs), optical storage disks such as compact disks (CDs) and flash-memory solid state drives (SSDs).
In the HDD, information is stored on magnetic platters rotating at a high speed and is read from, and written to the platters by a block of read/write heads. A microcontroller controls the movement of the heads relative to the platters, communicates with an external interface, and works with a disk cache buffer. Data can be stored in different parts of the platters and when the workload is random or nearly random it may take significant amounts of time to move the heads to the necessary location above the platter. Reordering write requests and look-ahead reading can increase performance significantly in HDD systems.
Logical block addressing (LBA) is commonly used to specify the location of blocks of data in a storage device. An LBA can refer either to an address or to a block (i.e. an index) with the first block being LBA=0, the second being LBA=1, and so on. The LBA scheme replaces earlier addressing schemes such as the cylinder-head-sector (CHS) scheme, which exposed physical details of the storage device to the operating system software. Logical blocks may typically be 512 or 1024 bytes (ISO 9660 CDs use 2048-byte blocks). System calls requiring block-level I/O pass LBA definitions to the storage device drivers. For some simple cases, a logical block size may be the same size as the smallest physical sectors that can be read from or written to the storage device.
In SSDs, flash memories based on NAND (or NOR) logic, store data in a few chips governed by a microcontroller. SSDs have a faster read time (i.e. the necessary cell or cells only have to be found and read) but a relatively slower write time (i.e. existing data must be erased from the cell or cells before writing new data into it). There are no spinning disks or read/write heads to worry about so access latency is less of an issue than with HDDs.
In order to facilitate higher performance through reordering of data transfer requests, queuing techniques such as Native Command Queuing (NCQ) have been introduced (e.g. for use in Serial ATA (Advanced Technology Attachment) HDDs) to allow optimization of the order that read and write commands are executed. One advantage of queuing for SSDs is that multiple commands can be delivered to the devices so that they aren't stalled when they complete a set of commands. There are also massively parallel implementations that benefit from having as much data as possible to transfer.
A host controller interface (e.g. an Advanced Host Controller Interface (AHCI) for a Serial ATA (SATA) device, or a Non-Volatile Memory Host Controller Interface (NVMHCI) for a flash memory storage device) is a hardware mechanism that allows software to communicate with devices (such as host bus adapters) through a system memory structure in order to take advantage of techniques such as NCQ.
Many modern operating systems such as Microsoft® Windows®, Berkeley Software Distribution (BSD, sometimes called Berkeley Unix) and Linux® provide support for a host controller interface such as AHCI, but such an interface may only support a limited amount of (i.e. 32) in-flight commands in the command queue and may generate a system interrupt for every completed request. Typically, many of the requests or commands could naturally be satisfied and completed together, and as devices increase in performance, they may have the capacity to consume more commands. SCSI protocols, on the other hand, may permits up to 264 commands to be queued but implementations supporting such long queues may be expensive and protocol overhead may be significantly greater than in AHCI.
To date, more efficient methods, structures and systems for servicing larger numbers of storage-device transfer requests have not been fully explored.